Chapter 27
Combinatorial Maps

Guillaume Damiand

Table of Contents

27.1   Introduction

A d-dimensional combinatorial map is a data structure representing an orientable subdivided d-dimensional object obtained by taking dD cells, and allowing to glue dD cells along (d-1)D cells. It provides a description of all the cells of the subdivision (for example vertices and edges), together with incidence and adjacency relationships. This package is a generalization of the halfedge data structure to higher dimension.¹

We denote i-cell for an i-dimensional cell (for example in 3D, 0-cells are vertices, 1-cells are edges, 2-cells are facets, and 3-cells are volumes). A boundary relation is defined on these cells, giving for each i-cell c the set of (i-1)-cells contained in the boundary of c. Two cells c1 and c2 are incident if there is a path of cells, starting from the cell of biggest dimension to the other cell, such that each cell of the path (except the first one) belongs to the boundary of the previous cell in the path. Two i-cells c3 and c4 are adjacent if there is an (i-1)-cell incident to both c3 and c4. You can see an example of a 2D object and a 3D object in Figure 27.1 showing some cells of the subdivision and some adjacency and incidence relations.

A combinatorial map is an edge-centered data structure describing the cells and the incidence and adjacency relations, using only one basic element called dart, and a set of pointers between these darts. A dart can be thought as a part of an oriented edge (1-cell), together with a part of incident cells of dimensions 0, 2, 3, … , d. When a dart d0 describes a part of an i-cell c, we say that d0 belongs to c, and that c contains d0. Let us look at the example in Figure 27.2 showing the 2D and 3D combinatorial maps describing the two objects given in Figure 27.1.

First let us start in 2D (Figure 27.2 (Left)). Facet f1 is described by four darts. These darts are linked together with pointers. Starting from a dart and following a β₁ pointer, we get to a dart which belongs to the same facet but to the next edge (1-cell, which explains the index 1 of β₁). Starting from any dart and following β₁ pointers, we can reach exactly all the darts describing the facet. Starting from a dart and following a β₂ pointer, we get to a dart which belongs to the same edge but to the neighboring facet (2-cell, which explains the index 2 of β₂). Starting from any dart and following β₂ pointers, we can reach exactly all the darts describing the edge (in 2D one or two darts).

Things are slightly different for vertices. Indeed, each β_i points to a dart belonging to a different i-cell, but also to a different 0-cell (vertex). This is so because two linked darts have opposite orientations. For this reason, starting from any dart belonging to a vertex v, we have to follow β₂ then β₁ to reach exactly the darts describing the vertex v. In fact, by composing two β_is, we always obtain a dart belonging to the same vertex (if we do not start by following a β₁ pointer).

The main interest of combinatorial map definition based on darts and β_i pointers is to be able to increase the dimension "only" by adding new pointers. We can verify this fact by studying the 3D example (Figure 27.2 (Right)). In addition to β₁ and β₂ of the 2D case, there is a new pointer β₃.

If we take a closer look at the central edge e4 shown in Figure 27.3 (Left), we can see that it is described by six darts linked together. Starting from a dart and following a β₃ pointer, we get to a dart which belongs to the same edge, to the same facet, but to the neighboring volume (a 3-cell, which explains the index 3 in β₃). Similarly, starting from a dart and following a β₂ pointer, we get to a dart which belongs to the same edge, to the same volume, but to the neighboring facet (2-cell). Starting from any of these six darts and following β₂ and β₃ pointers, we can reach exactly the six darts describing edge e4.

For facets, by following a β₁ pointer, we get to a dart which belongs to the same facet, to the same volume, but to the next edge (1-cell, which explains the index 1 of β₁). Starting from any dart and following β₁ and β₃ pointers, we can reach exactly all the darts describing the facet (see Figure 27.3 (Right)). For volumes, starting from any dart and following β₁ and β₂ pointers, we can reach exactly all the darts describing the volume.

For vertices, we have to follow β₂ then β₁, and β₃ then β₁ to reach exactly the darts describing the vertex v. Indeed, as in 2D, we have to compose two β_is to obtain a dart belonging to the same vertex (if we do not start by following a β₁ pointer).

In some cases, the general rule that by following a β_i we get a dart which belongs to the neighboring i-cell is not true, as for example for darts belonging to the boundary of the represented object. For example, in Figure 27.1 (Left), any dart d0 that does not belong to edge e1, e2 and e3 belongs to a 2-cell, and there is no neighboring facet along the edge containing d0. Another example is in Figure 27.1 (Right), for any dart d0 that belongs to facet f5. d0 belongs to volume vol2, but there is no neighboring volume along this facet. The general rule is also not true for unbounded cells. For example if we remove a dart in Figure 27.2 (Left), we obtain an unbounded facet having a dart without next dart for β₁, and if we remove a facet in Figure 27.2 (Right), we obtain an unbounded volume having some darts without neighboring facet for β₂. In such a case, there is a particular value called ∅ used to describe that a dart d0 is not linked to another dart in dimension i.

Combinatorial maps are defined in any dimension. A 0D combinatorial map is a set of isolated darts describing isolated vertices. A 1D combinatorial map describes paths or cycles of darts corresponding to paths or cycles of edges, and equivalent to double linked lists. The most useful cases are 2D and 3D combinatorial maps. Since 2D combinatorial maps are equivalent to halfedge data structure, notions are illustrated in 3D in the following examples to help the reader understand this specific case. But it is important to keep in mind that one main interest of combinatorial maps is their generic definition in any dimension, and that everything presented in this manual is valid in any dimension.

A dD combinatorial map is useful when you want to describe dD objects and the adjacency relations between these objects, and you want to be able to efficiency traverse these objects by using the different relations. For example, we can use a 3D combinatorial map to describe a 3D segmented image: each 3-cell corresponds to a region in the image and each 2-cell corresponds to a contact area between two regions.

A combinatorial map does not contain any geometrical information. However, this package allows to associate any information to the cells of the combinatorial map. A specific information, which is often used in practice, consists in adding linear geometry to a combinatorial map by associating a point to each vertex of the map²: this is the object of the Linear_cell_complex package. This package can for example be useful to describe 3D buildings as set of walls, rooms, doors and windows (both combinatorial and geometrical descriptions) and all the adjacency relations between these elements allowing for example to move a camera in a given building from rooms to rooms by traversing doors.

27.2   Data Structure Presentation

In this section, we describe dD combinatorial maps in terms of data structure and operations. Mathematical definitions are provided in Section 27.7, and a package description is given in Section 27.3.

27.2.1   Combinatorial Map and Darts

A dD combinatorial map is a set of darts D. A dart d0 is an element that can be linked with d+1 darts by pointers called β_i, with 0≤i≤d. Dart d0 is said i-free when β_i(d0)= ∅ . Each β_i, for 2≤i≤d, is its own inverse, i.e., if dart d0 is not i-free, then β_i(β_i(d0))=d0. This is different for β₀ and β₁: β₀ is the inverse of β₁, i.e., if darts d1 and d2 are such that β₁(d1)=d2, then β₀(d2)=d1. Given dart d1, if there is no dart d2 such that β₁(d2)=d1, then β₀(d1)= ∅ . ∅ is a constant, which does not belong to the set of darts D of the combinatorial map. However, by definition ∅ is linked with itself for all β_is: ∀i, 0≤i≤d, β_i( ∅ )= ∅ .

A combinatorial map is without i-boundary if there is no i-free dart, and it is without boundary if it is without i-boundary for all dimensions 1≤i≤d.

We show in Figure 27.4 a 3D object and the corresponding 3D combinatorial map. This map has 40 darts represented by arrows, some darts being numbered. In this combinatorial map, we have for example β₁(1)=2, β₂(1)=10, and β₃(1)=5. This combinatorial map is without 1-boundary and 2-boundary, but has some 3-boundary, because some darts are 3-free, for example β₃(10)= ∅ and β₃(12)= ∅ .

27.2.2   Cells as Sets of Darts

A cell in a dD combinatorial map is implicitly represented by a subset of darts. In this section, we will see how to retrieve all cells containing a given dart, how to retrieve all darts belonging to a cell containing a given dart, and how incidence and adjacency relations are defined in terms of darts.

The first important property of a combinatorial map is that each dart belongs to an i-cell, ∀i, 0≤i≤d. For example in 3D, a dart belongs to a vertex, an edge, a facet, and a volume. This means that a 3D combinatorial map containing an isolated dart contains exactly one vertex, one edge, one facet and one volume.

The second important property is that cells of a combinatorial map correspond to specific orbits. Given a set S⊆{β₁,…,β_d} and a dart d0, the orbit ⟨S⟩(d0) is the set of darts that can be reached from d0 by following any combination of any β_i's in S and their inverses (to simplify notations, we can use for example ⟨β₁,β₄⟩(d0) to denote ⟨S⟩(d0) with S={β₁,β₄}).

Given a dart d0, in general, β_i(d0) (with 1≤i≤d) belongs to the same cells as d0, only the i-cell and 0-cell are different. There are two exceptions: (1) if d0 is i-free, then β_i(d0)= ∅ ; (2) if β_i(d0) belongs to the same i-cell as d0 (case of multi-incidence). For example if an edge is an isolated loop, it is incident twice to the same vertex, then given a dart d0 belonging to this edge, β₁(d0) goes to the next edge, which is in fact the same edge.

Since β_i(d0) (with 1≤i≤d) allows to change the current i-cell, all the darts that can be reached from d0 by using any combination of β_j's, ∀j, 1≤j≤d and j≠i and their inverse are contained in the same i-cell as d0. The i-cell containing d0 is defined in terms of orbit by ⟨β₁,…,β_i-1,β_i+1,…,β_d⟩(d0).

There is a special case for vertices. Given a dart d0, the set of darts contained in the same vertex as d0 are the darts that can be reached from d0 by using any combination of β_i°β_j, ∀i,j, 1≤i<j≤d, and their inverse. The 0-cell containing d0 is defined in terms of orbit by ⟨{β_i°β_j|∀i,j: 1≤i<j≤d}⟩(d0).

Orbit ⟨β₁,…,β_d⟩(d0) is the connected component containing dart d0. A combinatorial map is connected if this set is equal to the set of all the darts of the combinatorial map.

A last important property of cells is that for all dimensions i the set of i-cells forms a partition of the set of darts D, i.e. for any i, the union of the sets of darts of all the i-cells is equal to D, and the sets of darts of two different i-cells are disjoint.

Let us give some examples of cells in 3D, for the 3D combinatorial map of Figure 27.4:

• All the darts belonging to the same edge can be obtained by any combination of β₂ and β₃: for example edge e of the object corresponds in the combinatorial map to the set of darts {1,5,9,10}. Given any dart belonging to this edge, we retrieve all the other darts by, for example, a breadth-first traversal. In terms of orbits, this 1-cell corresponds to ⟨β₂,β₃⟩(1).

• All the darts belonging to the same facet can be obtained by any combination of β₁ and β₃: for example facet f2 corresponds in the combinatorial map to the set of darts {1,2,3,4,5,6,7,8}. Facet f1 corresponds to the set of darts {10,11,12,13}. Note that these last darts are 3-free since there is no other volume sharing this facet. In terms of orbits, f2 corresponds to ⟨β₁,β₃⟩(1) and f1 corresponds to ⟨β₁,β₃⟩(10).

• All the darts belonging to the same volume can be obtained by any combination of β₁ and β₂: for example volume vol1 corresponds in the combinatorial map to the set of the twenty-four darts representing the cube. In terms of orbits, vol1 corresponds to ⟨β₁,β₂⟩(1).

• All the darts belonging to the same vertex can be obtained by any combination of β₁°β₂, β₁°β₃ and β₂°β₃ and their inverse functions. In our example, vertex v of the object corresponds in the combinatorial map to the set of darts {1,6,9,11,14,15}. Starting from dart 1, we obtain for example dart 14=(β₁°β₂)^-1(1)=β₂°β₀(1), dart 11=β₁°β₂(1), and dart 9=β₂°β₃(1). Intuitively, the set of darts corresponding to a vertex contains all the darts represented by arrows starting from this vertex. In terms of orbits, v corresponds to ⟨β₁°β₂, β₁°β₃, β₂°β₃⟩(1).

Using this definition of cells as sets of darts, we can retrieve all the incidence and adjacency relations between the cells of the subdivision in a combinatorial map. Two cells are incident if the intersection of their two sets of darts is non empty (whatever the dimension of the two cells). Two i-cells c1 and c2, 1≤i≤d, are adjacent if there is d1∈c1 and d2∈c2 such that d1=β_i(d2) (or d2=β_i(d1) for i=1).

In the example of Figure 27.4, vertex v and edge e are incident since the intersection of the two corresponding sets of darts is {1,9}≠∅. Vertex v is incident to facet f2 since the intersection of the two corresponding sets of darts is {1,6}≠∅. Edge e and facet f1 are incident since the intersection of the two corresponding sets of darts is {10}≠∅. Finally, facets f1 and f2 are adjacent because 10∈f1, 1∈f2 and 10=β₂(1).

We can consider i-cells in a dimension d' with i≤d'≤ d. The idea is to consider the i-cells as if the combinatorial map was in d' dimension. For that, we only take into account the β_js for j≤d'. The i-cell containing d0 in dimension d' is the orbit ⟨β₁,…,β_i-1,β_i+1,…,β_d'⟩(d0), and the 0-cell is the orbit ⟨{β_i°β_j|∀i,j: 2≤i<j≤d'}⟩(d0). By default, i-cells are considered in dimension d, the dimension of the combinatorial map.

In the example of Figure 27.4, the 2-cell containing dart 1 is facet f2 which is the set of darts {1,2,3,4,5,6,7,8}. If we consider the same 2-cell in dimension 2, we obtain the set of darts {1,2,3,4}. Intuitively we "forget" β₃ and we obtain the set of darts of the facet containing dart 1 restricted to the volume containing this dart.

27.2.3   How to Associate Information to Cells

Combinatorial maps only describe the cells of the subdvision, and all the incidence and adjacency relations between these cells. This is not enough for many applications which need to associate information to cells. This can be geometric or non-geometric information, such as 3D points associated to vertices, the edge length associated to edges, or a color or normal to a facet.

To answer this need, a combinatorial map allows to create attributes which are able to store any information, and to associate attributes to cells of the combinatorial map. We denote i-attributes for the attributes associated with i-cells. Attributes may exist for only some of the dimensions, and if they exist for dimension i, they do not necessarily exist for each of the i-cells. More precisely, i-attributes are associated to i-cells by an injection:

• two different i-cells are associated to two different i-attributes;
• an i-cell may have no associated i-attribute.

Since i-cells are not explicitely represented in combinatorial maps, the association between i-cells and i-attributes is transferred to darts: if attribute a is associated to i-cell c, all the darts belonging to c are associated to a.

We can see two examples of combinatorial maps having some attributes in Figure 27.5. In the first example (Left), a 2D combinatorial map has 1-attributes containing a float, for example corresponding to the length of the associated 1-cell, and 2-attributes containing a color in RGB format. In the second example (Right), a 3D combinatorial map has 2-attributes containing a color in RGB format.

27.2.4   Combinatorial Map Properties

There are some conditions that a combinatorial map must satisfy to be valid. Some of them have already been given about the β pointers (see Section 27.2.1) and about the association between darts and attributes (see Section 27.2.3).

There is an additional condition related to the type of represented objects, which are quasi-manifold orientable dD objects. A dD quasi-manifold is an object obtained by taking some isolated d-cells, and allowing to glue d-cells along (d-1)-cells. It is orientable if it is possible to embed it in the Euclidean space and to define a global "left" and "right" direction in each point of the embedded object. In 2D, quasi-manifolds are manifolds, but this is no longer true in higher dimension as we can see in the example presented in Figure 27.6. In this example, the object to the right is not a manifold since the neighborhood of the point p in the object is not homeomorphic³ to a 3D ball.

Combinatorial maps can only represent quasi-manifolds due to the definition of β pointers. As we have seen in Section 27.2.2, β_i(d0) (with 1≤i≤d) belongs to the same cells as d0, only the i-cell and 0-cell are different. In other words, β_i links two i-cells that share a common (i-1)-cell: it is not possible to link more than two i-cells along a same (i-1)-cell. For this reason, it is not possible to describe non quasi-manifold objects as those shown in Figure 27.7 by combinatorial maps.

Due to this additional condition, any objects can not be represented by a combinatorial map but only orientable quasi-manifolds. We need to study now the inverse relation. Does any set of darts linked together by β_i's, with 0≤i≤d correspond to a quasi-manifold? As we can see in Figure 27.8, the answer is no.

In the first example (Left), there are two 3-cells (one to the left for the cube, a second to the right for the pyramid) which are "partially adjacent" along one 2-cell. Indeed, only two darts of the 2-cell are linked by β₃. We have β₃(1)=5 and β₃(4)=6 (and reciprocally). This configuration is not possible in a quasi-manifold: two d-cells are always glue along an "entire" (d-1)-cells.

But as we can see in the second example (Right), the condition that all the darts of the cell are linked in not sufficient. Indeed, in this example, all the darts of the 2-cell between the cube and the pyramid are linked together by β₃. However, this configuration does not correspond to an orientable 3D quasi-manifold. Indeed, the operation of gluing two d-cells along one (d-1)-cell must preserve the initial (d-1)-cell.

To avoid these two kinds of configurations, conditions are added on β pointers compositions (see Section 27.7, condition (4) of the definition of combinatorial maps). Intuitively these conditions say that if two darts are linked by β_i, then all the required darts are linked by β_i two by two in such a way that neighborhood relations are preserved.

We say that a combinatorial map is valid if it satisfies all the conditions on β pointers and on association between darts and attributes. High level operations provided on combinatorial maps ensure that these conditions are always satisfied. Sometimes, it can be useful to use low level operations in a specific algorithm, for example to modify locally a combinatorial map in a really fast way. In such a case, additional operations may be needed to restore these validity conditions.

27.3   Software Design

The diagram in Figure 27.9 shows the different classes of the package. Combinatorial_map is the main class (see Section 27.3.1). It allows to manage darts (see Section 27.3.3) and attributes (see Section 27.3.4). Users can customize a combinatorial map thanks to an items class (see Section 27.3.2), which defines the dart type and the attribute types. These types may be different for different dimensions, and they may also be void. The darts and attributes are accessed through handles. A handle is a model of the Handle concept, thus supporting the two dereference operators operator* and operator->.

27.3.1   Combinatorial Maps

The class Combinatorial_map<d,Items,Alloc> is a model of the CombinatorialMap concept. It has three template parameters standing for the dimension of the combinatorial map (an unsigned int), an items class (a model of the CombinatorialMapItems concept), and an allocator which must be a model of the allocator concept of the STL. Default classes are provided for the items and the allocator classes.

The main role of the class Combinatorial_map is the storage and the management of darts. It allows to create or remove an isolated dart from the combinatorial map. The Dart_handle type defines a handle to the type of used darts (given in the items class). Combinatorial_map provides several ranges which allow to iterate over specific subsets of darts of the combinatorial map (see Section 27.4.1). It also defines several methods to link and to unlink darts by β_is (see Section 27.5.1). We said that a dart d0 is i-free if β_i(d0)= ∅ . The ∅ constant is represented in the class Combinatorial_map through a static const Dart_handle called null_dart_handle. Finally, some high level operations are defined as global functions taking a Combinatorial_map as argument (see Section 27.5.2)

The second role of the class Combinatorial_map is the storage and the management of attributes. It allows to create or remove an attribute, and provides methods to associate attributes and cells. A range is defined for each i-attribute allowing to iterate over all the i-attributes of the combinatorial map. Finally, Combinatorial_map defines several types allowing to manage the attributes. We can use Combinatorial_map::Attribute_handle<i>::type for a handle to the i-attributes (and the const version Combinatorial_map::Attribute_const_handle<i>::type) and Combinatorial_map::Attribute_type<i>::type for the type of the i-attributes.

27.3.2   Combinatorial Map Items

The CombinatorialMapItems concept defines dart and attribute types of a combinatorial map. It contains one inner class named Dart_wrapper, having one template parameter, CMap, a model of CombinatorialMap concept. The Dart_wrapper<CMap> class provides two local types: Dart which must be a model of the Dart concept, and Attributes which defines the attributes and their types.

The Attributes tuple must contain at most d+1 types (one for each possible cell dimension of the combinatorial map). Each type of the tuple must be either a model of the CellAttribute concept or void. The first type corresponds to 0-attributes, the second to 1-attributes and so on. If the i^th type in the tuple is void, (i-1)-attributes are disabled: we say that (i-1)-attributes are void. Otherwise, (i-1)-attributes are enabled and have the given type: we say (i-1)-attributes are non void. If the size of the tuple is k, with k<dimension+1, ∀i: k≤i≤dimension, i-attributes are void.

The class Combinatorial_map_min_items<d> is a model of the CombinatorialMapItems concept which can be used for default behaviors. It defines CGAL::Dart<d,CMap> as type of dart, and Attributes as empty tuple.

27.3.3   Darts

The class Dart<d,CMap>, a model of the Dart concept, defines a dD dart. It has two template parameters standing for the dimension of the combinatorial map, and a model of the CombinatorialMap concept, which provides the two types Dart_handle and Dart_const_handle.

Each instance d0 of Dart<d,CMap> stores the β_i pointers in an array of d+1 Dart_handle (because we describe also the β₀ pointer). It also stores the attributes associated to this dart in a tuple of CMap::Attribute_handle<i>::type, one for each non void i-attribute.

Methods are defined allowing to retrieve each β_i and each associated i-attribute of d0, and allowing to test if d0 dart is i-free.

Note that the use of the Dart class is not hard wired in the combinatorial map class. Users can provide their own model of the Dart concept, and pass it to the combinatorial map with the help of a custom item class.

27.3.4   Cell Attributes

The class Cell_attribute<CMap,Info_,Tag,OnMerge,OnSplit>, a model of the CellAttribute concept, represents an attribute associated with a cell of a combinatorial map. The template parameter CMap must be a model of the CombinatorialMap concept. The attribute stores a handle to one dart of its associated cell when the template parameter Tag is Tag_true. Info_ is the type of information stored in the attribute. It may be void. OnMerge and OnSplit must be either Null_functor, or models of the Binary Function concept having two references to a model of CellAttribute as type of both parameters and void as return type. There are two default parameters for OnMerge and OnSplit, which are Null_functor, a default parameter for Tag which is Tag_true, and a default parameter for Info_ which is void.

If Info_ is different from void, the class Cell_attribute contains two methods info() returning the information contained in the attribute (const and non const version). The information is returned by reference, thus the non const version allows the modification of the information.

Two attributes are merged when their corresponding cells are merged into one cell during some operation. In this case, the functor OnMerge is called, unless it is equal to Null_functor. This functor allows the user to define its own custom behavior when two attributes are merged (for example if the information is a color, we can compute the average color of the two initial attributes, and affect this value to the first attribute, see example in Section 27.6.4). Similarly, the functor OnSplit is called when one attribute is split in two, because its corresponding cell is split in two during some operation, unless it is equal to Null_functor. In any high level operation, OnMerge is called before to start the operation (i.e. before modifying the combinatorial map), and OnSplit is called when the operation is finished (i.e. after all the modifications were made).

What we said for the dart also holds for the cell attribute. The combinatorial map can be used with any user defined model of the CellAttribute concept.

27.3.5   Example of Combinatorial Map Definition

Here comes an example of two combinatorial map definitions. The first case Example_cmap4 defines a 4D combinatorial map which uses all the default values (Dart and Combinatorial_map_min_items). The second example Example_custom_cmap3 uses its own model of the CombinatorialMapItems concept. In this model, the type of dart is Dart<3,CMap>, thus a dart is in 3D, and an attribute containing an integer is associated to edges.

typedef CGAL::Combinatorial_map<4> Example_cmap4;

struct Example_items_3
{
   template <class CMap>
   struct Dart_wrapper
   {
     typedef CGAL::Dart<3, CMap> Dart;
     typedef CGAL::Cell_attribute<CMap, int> Edge_attrib;
     typedef CGAL::cpp0x::tuple<void,Edge_attrib> Attributes;
   };
};
typedef CGAL::Combinatorial_map<3, Example_items_3> Example_custom_cmap3;

27.4   Iteration and Creation Operations

An important operation in combinatorial maps consists in iterating over specific subsets of darts or over attributes. For that, several ranges are offered (see Section 27.4.1). A range is a model of the Range concept, thus supporting the two methods begin() and end() allowing to iterate over all the elements in the range. Several global functions allow to create specific configurations of darts into a combinatorial map (see Section 27.4.2). Darts can be marked during operations, for example when performing a breadth-first search traversal, thanks to Boolean marks (see Sections 27.4.3). In the following, we denote by dh0, dh1, dh2 the dart handles for the darts d0, d1, d2, respectively. That is d0 == *dh0.

27.4.1   Iterating over Orbits, Cells, and Attributes

The combinatorial map offers iterators to traverse the darts of a specific orbit, to traverse all darts of one cell, or one dart per cell, and to traverse all i-attributes.

Instead of the begin()/end() member function pair as we know it from STL containers, and from most Cgal data structures, the combinatorial map defines range classes which are all models of the Range concept.

There are three different categories of dart range classes:

• Dart_range: range of all the darts of a combinatorial map;
• Dart_of_orbit_range<Beta...>: range of all the darts of the orbit ⟨Beta...⟩(d0) for a given d0. Beta... is a sequence of integers i₁,…,i_k, each i_j∈{0, … ,d}. These integers must satisfy: i₁<i₂<…<i_k, and (i₁≠0 or i₂≠1) (for example Dart_of_orbit_range<1,2> for the orbit ⟨β₁,β₂⟩(d0));
• Dart_of_cell_range<i,dim>: range of all the darts of the i-cell containing a given dart. The i-cell is considered in dimension dim (with 0≤dim≤d, dim=d by default), with 0≤i≤dim+1. If i=dim+1, Dart_of_cell_range<i,dim> is the range of all the darts of the connected component containing a given dart.

There are also two different classes of ranges containing one dart per i-cell. Note that in these classes, the dart of each i-cell can be any dart of the cell. Moreover, each i-cell (and j-cell in the second case) is considered in dimension dim (with 0≤dim≤d, dim=d by default).

• One_dart_per_cell_range<i,dim>: range containing one dart of each i-cell of the combinatorial map, 0≤i≤dim+1 (for example One_dart_per_cell_range<2> for the range of one dart per 2-cell of the combinatorial map);
• One_dart_per_incident_cell_range<i,j,dim>: range containing one dart of each i-cell incident to the j-cell containing a given dart, with 0≤i≤dim+1 and 0≤j≤dim+1 (for example One_dart_per_incident_cell_range<0,3> for the range of one dart per vertex of the volume incident to the starting dart). If i=j, the range contains only the given dart.

The iterators of the Dart_range are bidirectional iterators, while the iterators of the other four ranges are forward iterators. The value type of all these iterators is Dart thus all these iterators can be directly used as Dart_handle.

Additionally, there is a range over non void i-attributes: Attribute_range<i>::type, having a bidirectional iterator with value type Attribute_type<i>::type.

For each range, there is an associated const range, a model of the ConstRange concept. You can find some examples of ranges in Section 27.6.1.

27.4.2   Construction Operations

Several global functions allow to create specific configurations of darts into a combinatorial map. Existing darts in the combinatorial map are not modified. Note that the dimension of the combinatorial map must be large enough: darts must contain all the β pointers used by the operation. All these functions take an instance of CombinatorialMap as first parameter (called cm) and return a Dart_handle to a new dart created during the operation.

• make_edge<CMap>(cm): creates an isolated edge (two darts linked by β₂); dimension must be greater or equal than two;
• make_combinatorial_polygon<CMap>(cm,lg): creates an isolated combinatorial polygon of length lg (lg darts linked by β₁), for lg>0; dimension must be greater or equal than one;
• make_combinatorial_tetrahedron<CMap>(cm): creates an isolated combinatorial tetrahedron (four combinatorial triangles linked together by β₂); dimension must be greater or equal than two;
• make_combinatorial_hexahedron<CMap>(cm): creates an isolated combinatorial hexahedron (six combinatorial quadrangles linked together by β₂); dimension must be greater or equal than two.

File: examples/Combinatorial_map/map_3_marks.cpp

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_constructors.h>
#include <CGAL/Combinatorial_map_operations.h>
#include <iostream>
#include <cstdlib>

typedef CGAL::Combinatorial_map<3> CMap_3;
typedef CMap_3::Dart_handle Dart_handle;

int main()
{
  CMap_3 cm;
  
  // 1) Reserve a mark.
  int mark = cm.get_new_mark();
  if ( mark==-1 )
    {
      std::cerr<<"No more free mark, exit."<<std::endl;
      exit(-1);
    }
  
  // 2) Create two tetrahedra.
  Dart_handle dh1 = make_combinatorial_tetrahedron(cm);  
  Dart_handle dh2 = make_combinatorial_tetrahedron(cm);

  // 3) 3-sew them.
  cm.sew<3>(dh1, dh2);
  
  // 4) Mark the darts belonging to the first tetrahedron.
  for  (CMap_3::Dart_of_cell_range<3>::iterator 
          it(cm.darts_of_cell<3>(dh1).begin()),
          itend(cm.darts_of_cell<3>(dh1).end()); it!=itend; ++it)
    cm.mark(it, mark);

  // 4) Remove the common 2-cell between the two cubes:
  // the two tetrahedra are merged.
  CGAL::remove_cell<CMap_3, 2>(cm, dh1);

  // 5) Thanks to the mark, we know which darts come from the first tetrahedron.
  unsigned int res=0;
  for (CMap_3::Dart_range::iterator it(cm.darts().begin()),
         itend(cm.darts().end()); it!=itend; ++it)
    {
      if ( cm.is_marked(it, mark) )
        ++res;
    }
  
  std::cout<<"Number of darts from the first tetrahedron: "<<res<<std::endl;
  cm.free_mark(mark);

  return EXIT_SUCCESS;
}

27.5   Modification Operations

Several operations allow to modify a given combinatorial map. There are two main categories of modification operations:

• Sew, link, unsew and unlink which modify some existing β pointers, without creating or removing darts (see Section 27.5.1);
• Removal and insertion of cells which modify both darts and β pointers (see Section 27.5.2).

27.5.1   Sewing Orbits and Linking Darts

The CombinatorialMap defines two groups of methods to modify the β pointers of existing darts.

• The sew and unsew methods iterate over two orbits in order to link or unlink specific darts two by two. Intuitively, a sew<i> operation glues two i-cells by identifying two of their (i-1)-cells (see example in Figure 27.10 where sew<3> is used to glue two 3-cells along one 2-cell). Reciprocally, a unsew<i> operation un-glues two i-cells which were glued along one of their (i-1)-cells. These methods guarantee that given a valid combinatorial map and a possible operation we obtain a valid combinatorial map as result of the operation.

• The link_beta and unlink_beta methods only modify the pointer of two darts: the obtained combinatorial maps may be not valid. These operations can be useful to use low level operations in a specific algorithm, for example to modify locally a combinatorial map in a really fast way. In such a case, additional operations may be needed to restore the validity conditions.

Linking two darts d1 and d2 by β_i, with 2≤i≤d and d1≠d2, consists in modifying two β_i pointers such that β_i(d1)=d2 and β_i(d2)=d1. For i=1, the modification is β₁(d1)=d2 (and thus β₀(d2)=d1 by definition of β₀); in this case we can have d1=d2 (a dart linked with itself corresponds to an edge which is a loop).

Reciprocally, unlinking a given dart d0 by β_i, with 2≤ i≤d, consists in modifying two β_i pointers such that β_i(β_i(d0))= ∅ and β_i(d0)= ∅ . For i=1, the modification is β₁(d0)= ∅ (and thus β₀(β₁(d0))= ∅ by definition of β₀). Note that is it possible to unlink a given dart for β_i only if it is not i-free.

The sew<i>(dh1,dh2) method consists mainly to link two by two several darts by β_i. This operation is possible only if there is a bijection f between all the darts of the orbit D1=⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(d1) and D2=⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(d2) satisfying: f(d1)=d2, and for all e∈D1, for all j∈{1,…,i-2,i+2,…,d}, f(β_j(e))=β_j^-1(f(e)). Intuitively, this condition ensures the validity of the combinatorial map by verifying that condition discussed in Section 27.2.4 will be satisfied after the operation. This condition can be tested by using the method is_sewable<i>(dh1,dh2). For example, the function is_sewable<i> would return false if we tried to sew a triangular facet with a quad facet. Note that given two darts d1 and d2, if there is such a bijection, it is uniquely defined. So giving the two darts as arguments of the sew<i> is enough to retrieve all the pairs of darts to link. If such a bijection exists, the sew<i>(dh1,dh2) operation consists only in linking by β_i each couple of darts d3 and d4 such that d3=f(d4).

In addition, the sew operation updates the associations between darts and non void attributes in order to guarantee that all the darts belonging to a given cell are associated with the same attribute (which is a condition of combinatorial map validity). For each couple of j-cells c1 and c2 that are merged into one j-cell during the sew, we have to update the two associated attributes attr1 and attr2. If both are NULL, there is nothing to do. If one is NULL and the other not, we only associate the non NULL attribute to all the darts of the resulting cell. When the two attributes are non NULL, we first apply functor On_merge on the two attributes attr1 and attr2 (see Section 27.3.4). Then, we associate the attribute attr1 to all darts of the resulting j-cell. Finally, attribute attr2 is removed from the combinatorial map.

Note that when the two attributes are non NULL, the first one is kept. But user can customize this behavior in order to update the information contained in the attributes according to its needs. For that, we can define a specific functor, and use it as template argument for OnMerge parameter of the Cell_attribute definition. This functor can for example copy the information of the second attribute in the information of the first one to make as if the second attribute is kept.

For example, in Figure 27.10, we want to 3-sew the two initial volumes. sew<3>(1,5) links by β₃ the pairs of darts (1,5), (2,8), (3,7) and (4,6), thus the combinatorial map obtained is valid. 2-attributes are updated so that all the darts belonging to the 2-cell containing dart 1 become associated to the same 2-attribute after the operation.

Similarly, unsew<i>(dh0) operation unlinks β_i for all the darts in the orbit ⟨β₁,…,β_i-2,β_i+2,…,β_d⟩(d0), and thus guarantees to obtain a valid combinatorial map. This operation is possible for any non i-free dart.

As for the sew operations, attributes are updated to guarantee that two darts belonging to two different j-cells are associated to two different j-attributes. If the unsew operation splits a j-cell c in two j-cells c1 and c2, and if c is associated to a j-attribute attr1, then this attribute is duplicated into attr2, and all the darts belonging to c2 are associated with this new attribute. Finally, we call the functor On_split on the two attributes attr1 and attr2 (see Section 27.3.4).

Let us consider the combinatorial map given in Figure 27.10 (Right). If we call unsew<3>(2), we obtain the combinatorial map in Figure 27.10 (Left) (except for the color of the attribute associated to the 2-cell {5,6,7,8} which would be #00ff00). The unsew<3> operation has duplicated the 2-attribute associated to the 2-cell {1,2,3,4,5,6,7,8} since this 2-cell is split in two after the unsew operation.

27.5.2   Removal and Insertion Operations

The following high level operations are defined as global functions taking an instance cm of CombinatorialMap as first argument. All these methods ensure that given a valid combinatorial map and a possible operation, the modified combinatorial map is also valid.

The first one is remove_cell<CMap,i>(cm,dh0) which modifies the combinatorial map to remove the i-cell containing dart d0, with 0≤i≤d. This operation is possible if i=d or if the given i-cell is incident to at most two (i+1)-cells which can be tested thanks to is_removable<CMap,i>(cm,dh0). If the removed i-cell was incident to two different (i+1)-cells, these two cells are merged into one (i+1)-cell. In this case, the On_merge functor is called if two (i+1)-attributes are associated to the two (i+1)-cells. If the i-cell is associated with a non void attribute, it is removed from the combinatorial map (see three examples on Figures 27.11, 27.13 and 27.14).

The inverse operation of the removal is the insertion operation. Several versions exist, sharing a common principle. They consist in adding a new i-cell "inside" an existing j-cell, i<j, by splitting the j-cell into several j-cells. Contrary to remove_cell<CMap,i>, is it not possible to define a unique insert_cell_i_in_cell_j<CMap,i,j> function because parameters are different depending on i and j.

insert_cell_0_in_cell_1<CMap>(cm,dh0) adds a 0-cell in the 1-cell containing dart d0. The 1-cell is split in two. This operation is possible if d0∈cm.darts() (see example on Figure 27.11).

insert_cell_0_in_cell_2<CMap>(cm,dh0) adds a 0-cell in the 2-cell containing dart d0. The 2-cell is split in triangles, one for each initial edge of the facet. This operation is possible if d0∈cm.darts() (see example on Figure 27.12).

insert_cell_1_in_cell_2<CMap>(cm,dh1,dh2) adds a 1-cell in the 2-cell containing darts d1 and d2, between the two 0-cells containing darts d1 and d2. The 2-cell is split in two. This operation is possible if d1∈⟨β₁⟩(d2) which can be tested thanks to is_insertable_cell_1_in_cell_2(cm,dh1,dh2). In the example on Figure 27.13, it is possible to insert an edge between darts d2 and d3, but it is not possible to insert an edge between d1 and d3.

insert_dangling_cell_1_in_cell_2<CMap>(cm,dh0) adds a 1-cell in the 2-cell containing dart d0, the 1-cell being attached by only one of its vertex to the 0-cell containing dart d0. This operation is possible if d0∈cm.darts().

insert_cell_2_in_cell_3<CMap>(cm,itbegin,itend) adds a 2-cell in the 3-cell containing all the darts between itbegin and itend, along the path of 1-cells containing darts in [itbegin,itend). The 3-cell is split in two. This operation is possible if all the darts in [itbegin,itend) form a closed path inside a same 3-cell which can be tested thanks to is_insertable_cell_2_in_cell_3(cm,itbegin,itend) (see example on Figure 27.14).

Some examples of use of these operations are given in Section 27.6.2.

27.6   Examples

27.6.1   A 3D Combinatorial Map

In this example, a 3-dimensional combinatorial map is constructed. Two combinatorial tetrahedra are created, then the numbers of cells of the combinatorial map are displayed, and the validity of the combinatorial map is checked. Then, we illustrate the use of ranges to iterate over specific darts. The first loop enumerates all the darts of the first tetrahedron by using the range Dart_of_orbit_range<1,2>, and the second loop enumerates all the darts of the facet containing dart dh2 by using the range Dart_of_orbit_range<1>.

File: examples/Combinatorial_map/map_3_simple_example.cpp

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_constructors.h>
#include <iostream>
#include <cstdlib>

typedef CGAL::Combinatorial_map<3> CMap_3;
typedef CMap_3::Dart_const_handle Dart_const_handle;

  int main() 
  { 
    CMap_3 cm;

    // Create two tetrahedra.  
    Dart_const_handle dh1 = CGAL::make_combinatorial_tetrahedron(cm); 
    Dart_const_handle dh2 = CGAL::make_combinatorial_tetrahedron(cm);
  
    // Display the combinatorial map characteristics.
    cm.display_characteristics(std::cout); 
    std::cout<<", valid="<<cm.is_valid()<<std::endl;
  
    unsigned int res = 0; 
    // Iterate over all the darts of the first tetrahedron.  
    // Note that CMap_3::Dart_of_orbit_range<1,2> in 3D is equivalent to 
    // CMap_3::Dart_of_cell_range<3>.  
    for  (CMap_3::Dart_of_orbit_range<1,2>::const_iterator
          it(cm.darts_of_orbit<1,2>(dh1).begin()),
          itend(cm.darts_of_orbit<1,2>(dh1).end()); it!=itend; ++it) 
       ++res;

    std::cout<<"Number of darts of the first tetrahedron: "
             <<res<<std::endl;

    res = 0; 
    // Iterate over all the darts of the facet containing dh2.  
    for (CMap_3::Dart_of_orbit_range<1>::const_iterator
         it(cm.darts_of_orbit<1>(dh2).begin()),
         itend(cm.darts_of_orbit<1>(dh2).end()); it!=itend; ++it) 
       ++res;
  
    std::cout<<"Number of darts of the facet containing dh2: "
             <<res<<std::endl; 

    return EXIT_SUCCESS;
}

The output is:

#Darts=24, #0-cells=8, #1-cells=12, #2-cells=8, #3-cells=2, #ccs=2, valid=1
Number of darts of the first tetrahedron: 12
Number of darts of the facet containing dh2: 3

which gives the number of darts of the combinatorial map, the numbers of different cells, the number of connected components, and finally a Boolean showing the validity of the combinatorial map (a tetrahedron is made up of 12 darts because there are 3 darts per facet and there are 4 facets).

Note the creation in the for loops of the two instances of Dart_of_orbit_range::const_iterator: it is the current iterator, and itend an iterator to the end of the range. Having itend avoids calling cm.darts_of_orbit<1,2>(dh1).end() again and again as in the following example (which is a bad solution):

  for (CMap_3::Dart_of_orbit_range<1,2>::const_iterator 
       it(cm.darts_of_orbit<1,2>(dh1).begin());
       it!=cm.darts_of_orbit<1,2>(dh1).end()); ++it)
  {...}

27.6.2   High Level Operations

This example shows some uses of high level operations. First we create a combinatorial hexahedron, the combinatorial map obtained is shown in Figure 27.15 (Left). Then we insert two 1-cells along two opposite 2-cells of the hexahedron. The combinatorial map obtained is shown in Figure 27.15 (Middle). Finally, we insert a 2-cell in the diagonal of the hexahedron in order to split it into two parts. We obtain the combinatorial map shown in Figure 27.15 (Right). We display the characteristics of the combinatorial map and check its validity.

The second part of this example removes the inserted elements. First we remove the inserted 2-cell, then the two inserted 1-cells. We get back the initial combinatorial hexahedron, which is verified by displaying once again the characteristics of the combinatorial map.

File: examples/Combinatorial_map/map_3_operations.cpp

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_constructors.h>
#include <CGAL/Combinatorial_map_operations.h>
#include <iostream>
#include <cstdlib>

typedef CGAL::Combinatorial_map<3> CMap_3;
typedef CMap_3::Dart_handle        Dart_handle;

int main()
{
  CMap_3 cm;

  // Create one combinatorial hexahedron.
  Dart_handle dh1 = CGAL::make_combinatorial_hexahedron(cm);

  // Add two edges along two opposite facets.
  CGAL_assertion( CGAL::is_insertable_cell_1_in_cell_2
                        (cm,dh1->beta(1),dh1->beta(0)) );

  CGAL::insert_cell_1_in_cell_2(cm,dh1->beta(1),dh1->beta(0));
  CGAL_assertion( cm.is_valid() );

  Dart_handle dh2=dh1->beta(2)->beta(1)->beta(1)->beta(2);

  CGAL_assertion( CGAL::is_insertable_cell_1_in_cell_2
                        (cm,dh2,dh2->beta(1)->beta(1)) );
  
  CGAL::insert_cell_1_in_cell_2(cm,dh2,dh2->beta(1)->beta(1));
  CGAL_assertion( cm.is_valid() );

  // Insert a facet along these two new edges plus two initial edges
  // of the hexahedron.
  std::vector<Dart_handle> path;
  path.push_back(dh1->beta(1));
  path.push_back(dh1->beta(0)->beta(2)->beta(1));
  path.push_back(dh2->beta(0));
  path.push_back(dh2->beta(2)->beta(1));
  
  CGAL_assertion( (CGAL::is_insertable_cell_2_in_cell_3
                   (cm,path.begin(),path.end())) );

  Dart_handle dh3=CGAL::insert_cell_2_in_cell_3(cm,path.begin(),path.end());
  CGAL_assertion( cm.is_valid() );
  
  // Display the combinatorial map characteristics.
  cm.display_characteristics(std::cout) << ", valid=" << 
    cm.is_valid() << std::endl;

  // We use the removal operations to get back to the initial hexahedron.
  CGAL_assertion( (CGAL::is_removable<CMap_3, 2>(cm,dh3)) );
  CGAL::remove_cell<CMap_3,2>(cm,dh3);
  CGAL_assertion( cm.is_valid() );

  CGAL_assertion( (CGAL::is_removable<CMap_3, 1>(cm,dh1->beta(1))) );
  CGAL::remove_cell<CMap_3,1>(cm,dh1->beta(1));
  CGAL_assertion( cm.is_valid() );
  
  CGAL_assertion( (CGAL::is_removable<CMap_3, 1>(cm,dh2->beta(0))) );
  CGAL::remove_cell<CMap_3,1>(cm,dh2->beta(0));
  CGAL_assertion( cm.is_valid() );
  
  // Display the combinatorial map characteristics.
  cm.display_characteristics(std::cout) << ", valid=" 
                                        << cm.is_valid() << std::endl;

  return EXIT_SUCCESS;
}

The output is:

#Darts=36, #0-cells=8, #1-cells=14, #2-cells=9, #3-cells=2, #ccs=1, valid=1
#Darts=24, #0-cells=8, #1-cells=12, #2-cells=6, #3-cells=1, #ccs=1, valid=1

The first line gives the characteristics of the combinatorial map after all the insertions (the combinatorial map drawn in Figure 27.15 (Right)). There are two 3-cells (since the combinatorial hexahedron was split in two by the 2-cell insertion), nine 2-cells (since two 2-cells of the original hexahedron were split in two by the two 1-cell insertions, and a new 2-cell was created during the 2-cell insertion), fourteen 1-cells (since there are two new 1-cells created by the 1-cell insertion) while the number of 0-cells remains unchanged.

The second line is the result after the removal operations. We retrieve the original combinatorial hexahedron since we have removed all the inserted elements.

27.6.3   A 4D Combinatorial Map

In this example, a 4-dimensional combinatorial map is used. Two tetrahedral cells are created and sewn by β₄. Then the numbers of cells of the combinatorial map are displayed, and its validity is checked.

By looking at these numbers of cells, we can see that the 4D combinatorial map contains only one 3-cell. Indeed, the sew<4> operation has identified by pairs all the darts of the two 3-cells by definition of the sew operation (see Section 27.5.1) which, in 4D, links by β₃ all the darts in ⟨β₁,β₂⟩(d1) and in ⟨β₁,β₂⟩(d2). The situation is similar (but in higher dimension) to the configuration where we have two triangles in a 3D combinatorial map, and you use sew<3> between these two triangles. The two triangles are identified since all their darts are linked by β₃, thus we obtain a 3D combinatorial map containing only one 3-cell. Note that this 3-cell is unbounded since the darts of the two triangles are all 2-free. In the 4D case, the 4-cell is unbounded since all its darts are 3-free.

In this example, we also illustrate how to use the basic methods to build "by hand" some specific configuration in a combinatorial map. In fact, these functions are already present in the package: function make_triangle(cm) is equivalent to CGAL::make_combinatorial_polygon(cm,3) and make_tetrahedron(cm) is equivalent to CGAL::make_combinatorial_tetrahedron(cm). If we want to create a 4D simplex, we must create five 3D simplexes, and sew them correctly two by two by β₃ (and so on if you want to create higher dimensional combinatorial map).

File: examples/Combinatorial_map/map_4_simple_example.cpp

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_constructors.h>
#include <iostream>
#include <cstdlib>

typedef CGAL::Combinatorial_map<4> CMap_4;
typedef CMap_4::Dart_handle Dart_handle;

Dart_handle make_triangle(CMap_4& amap)
{
 Dart_handle d1 = amap.create_dart();
 Dart_handle d2 = amap.create_dart();
 Dart_handle d3 = amap.create_dart();
 amap.link_beta<1>(d1,d2);
 amap.link_beta<1>(d2,d3);
 amap.link_beta<1>(d3,d1);
 return d1;
}
 
Dart_handle make_tetrahedral(CMap_4& amap)
{
  Dart_handle d1 = make_triangle(amap);
  Dart_handle d2 = make_triangle(amap);
  Dart_handle d3 = make_triangle(amap);
  Dart_handle d4 = make_triangle(amap);
  amap.link_beta<2>(d1, d2);
  amap.link_beta<2>(d3, d2->beta(0));
  amap.link_beta<2>(d1->beta(1), d3->beta(0));
  amap.link_beta<2>(d4, d2->beta(1));
  amap.link_beta<2>(d4->beta(0), d3->beta(1));
  amap.link_beta<2>(d4->beta(1), d1->beta(0));
  return d1;
}

int main()
{
  CMap_4 cm;
  Dart_handle d1 = make_tetrahedral(cm);
  Dart_handle d2 = make_tetrahedral(cm);
  
  cm.sew<4>(d1,d2);
  
  cm.display_characteristics(std::cout);
  std::cout<<", valid="<<cm.is_valid()<<std::endl;

  return EXIT_SUCCESS;
}

The output is:

#Darts=24, #0-cells=4, #1-cells=6, #2-cells=4, #3-cells=1, #4-cells=2, #ccs=1, valid=1

27.6.4   Combinatorial Map With Attributes

In the following example, we illustrate how to specify the 2-attributes in a 3D combinatorial map. For that, we define our own item class using CGAL::Dart<3,CMap> as type of dart, and CGAL::Cell_attribute<CMap,int,CGAL::Tag_true,Sum_functor,Divide_by_two_functor> as attributes which contain an int and which are associated to 2-cells of the combinatorial map.

Functors Sum_functor and Divide_by_two_functor define a custom behavior: when two attributes ca1 and ca2 are merged into ca1, the value of ca1 is the sum of the two initial values. When an attribute ca1 is split in the two attributes ca1 and ca2, the value of each attribute is half of the first value.

File: examples/Combinatorial_map/map_3_with_colored_facets.cpp

#include <CGAL/Combinatorial_map.h>
#include <CGAL/Combinatorial_map_constructors.h>
#include <CGAL/Combinatorial_map_operations.h>
#include <CGAL/Cell_attribute.h>
#include <iostream>
#include <algorithm>
#include <cstdlib>

struct Sum_functor
{
  template<class Cell_attribute>
  void operator()(Cell_attribute& ca1,Cell_attribute& ca2)
  { ca1.info()=ca1.info()+ca2.info(); }
};
struct Divide_by_two_functor
{
  template<class Cell_attribute>
  void operator()(Cell_attribute& ca1,Cell_attribute& ca2)
  {
    ca1.info()=(ca1.info()/2);
    ca2.info()=(ca1.info());
  }
};

struct Myitem
{
  template<class CMap>
  struct Dart_wrapper
  {
    typedef CGAL::Dart<3, CMap> Dart;
    typedef CGAL::Cell_attribute<CMap, int, CGAL::Tag_true,
                                 Sum_functor, Divide_by_two_functor>
    Facet_attribute;
    typedef CGAL::cpp0x::tuple<void,void,Facet_attribute> Attributes;
  };
};

typedef CGAL::Combinatorial_map<3,Myitem> CMap_3;
typedef CMap_3::Dart_handle               Dart_handle;

int main()
{
  CMap_3 cm;
  
  // Create 2 hexahedra.
  Dart_handle dh1 = make_combinatorial_hexahedron(cm);
  Dart_handle dh2 = make_combinatorial_hexahedron(cm);

  // 1) Create all 2-attributes and associated them to darts.
  for (CMap_3::Dart_range::iterator 
         it=cm.darts().begin(), itend=cm.darts().end();
         it!=itend; ++it)
    {
      if ( it->attribute<2>()==NULL )
        cm.set_attribute<2>(it, cm.create_attribute<2>());
    }  
  
  // 2) Set the color of all facets of the first hexahedron to 7.
  for (CMap_3::One_dart_per_incident_cell_range<2, 3>::iterator 
         it=cm.one_dart_per_incident_cell<2,3>(dh1).begin(), 
         itend=cm.one_dart_per_incident_cell<2,3>(dh1).end(); it!=itend; ++it)
    { it->attribute<2>()->info()=7; }
  
  // 3) Set the color of all facets of the second hexahedron to 13.
  for (CMap_3::One_dart_per_incident_cell_range<2, 3>::iterator it=
         cm.one_dart_per_incident_cell<2,3>(dh2).begin(),
         itend=cm.one_dart_per_incident_cell<2,3>(dh2).end(); it!=itend; ++it)
    { it->attribute<2>()->info()=13; }
  
  // 4) 3-Sew the two hexahedra along one facet.
  cm.sew<3>(dh1, dh2);

  // 5) Display all the values of 2-attributes.
  for (CMap_3::Attribute_range<2>::type::iterator 
         it=cm.attributes<2>().begin(), itend=cm.attributes<2>().end(); 
       it!=itend; ++it)
    {
      std::cout<<it->info()<<"; ";
    }
  std::cout<<std::endl;

  // 6) Insert a vertex in the facet between the two hexahedra.
  CGAL::insert_cell_0_in_cell_2(cm, dh2);

  // 7) Display all the values of 2-attributes.
  for (CMap_3::Attribute_range<2>::type::iterator 
         it=cm.attributes<2>().begin(), itend=cm.attributes<2>().end(); 
       it!=itend; ++it)
    {
      std::cout<<it->info()<<"; ";
    }
  std::cout<<std::endl;
  cm.display_characteristics(std::cout);
  std::cout<<", valid="<<cm.is_valid()<<std::endl;

  return EXIT_SUCCESS;
}

The output is:

20; 7; 7; 7; 7; 7; 13; 13; 13; 13; 13; 
2; 7; 7; 7; 7; 7; 2; 13; 13; 13; 13; 13; 5; 10; 
#Darts=64, #0-cells=13, #1-cells=24, #2-cells=14, #3-cells=2, #ccs=1, valid=1

Before the cm.sew<3>, each 2-cell of the first cube is associated with an attribute having 7 as value, and each 2-cell of the second cube with an attribute having 13 as value. During the cm.sew<3>, two 2-cells are merged, thus the functor Sum_functor is called on the two associated 2-attributes, and the value of the new 2-cell is the sum of the two previous one: 20.

Then we call CGAL::insert_cell_0_in_cell_2 on a dart which belong to this 2-cell. This method splits the existing 2-cell in k 2-cells, k being the number of 1-cells of the initial 2-cell (4 in this example). These splits are made consecutively, thus for the first split, we create a new attribute as copy of the initial one and call functor Divide_by_two_functor on these two attributes: the value of each attribute is thus 20/2=10. For the second split, the value of each attribute is thus 10/2=5, and for the last split the value of each attribute is thus 5/2=2 (remember that information contained in 2-attributes in an int). At the end, we obtain five 2-attributes with 7 as value, five 2-attributes with 13 as value, and four 2-attributes having respectively 2, 2, 5 and 10 as values.

27.7   Mathematical Definitions

The initial definition of combinatorial map in any dimension is given in [Lie91, Lie94]. But it allows only to represent objects without boundaries. This definition was extended [PABL07, Dam10] in order to allow to represent objects with boundaries, based on the notions of partial permutations and partial involutions.

Intuitively, a partial permutation on a finite set E is a mapping from E∪{ ∅ } to E∪{ ∅ } which is injective on the subset of the domain that does not map to ∅ . More precisely, a mapping p: E∪{ ∅ } → E∪{ ∅ } is a partial permutation defined on E if:

1. p( ∅ )= ∅ ;
2. ∀e1∈E, ∀e2∈E, p(e1)=p(e2)≠ ∅ ⇒ e1=e2.

The inverse p^-1 of this partial permutation is also a partial permutation and is defined by:

1. p^-1( ∅ )= ∅ ;
2. ∀e∈E, if it exists a∈E such that p(a)=e, then p^-1(e)=a, otherwise p^-1(e)= ∅ .

Let E be a set, and p a partial permutation on E. An element e is called a fixed point for p if p(e)=e. p is a partial involution if ∀e∈E: p(e)≠ ∅ ⇒ p(p(e))=e.

Now we can give the definition of a combinatorial map in any dimension. Let d≥0. A d-dimensional combinatorial map (or d-map) is a (d+1)-tuple M=(D,β₁,…,β_d) where:

1. D is a finite set of darts;
2. β₁ is a partial permutation on D;
3. ∀i, 2≤i≤d, β_i is a partial involution on D without fixed point;
4. ∀i: 0≤i≤d-2, ∀j: 3≤j≤d, i+2≤j, β_i°β_j is a partial involution.

A d-dimensional combinatorial map represents a subdivision of an orientable d-dimensional quasi-manifold. A dart is an abstract element which is only required to define partial permutations. The last line of the definition fixes constraints which guarantee the topological validity of the represented object, i.e., the fact that it is a quasi-manifold. This definition allows us to verify the validity of a given combinatorial map by checking if each item of the definition is satisfied.

Given a set of partial permutations S={f₁,…,f_k}, we denote by ⟨S⟩ the permutation group generated by {f₁,…,f_k} and whose group operation is the composition of partial permutations. The orbit ⟨f₁,…,f_k⟩(a) is the set of darts which can be obtained from a by elements of ⟨S⟩: ⟨f₁,…,f_k⟩(a)={φ(a)|φ∈⟨S⟩}\ { ∅ }.

Let d0∈D be a dart. Given i, 1≤i≤d, the i-cell containing d0 is ⟨β₁,…,β_i-1,β_i+1,…,β_d⟩(d0). The 0-cell containing d0 is ⟨{β_i°β_j|∀i,j: 1≤i<j≤d}⟩(d0).

27.8   Design and Implementation History

The code of this package is inspired by Moka, a 3D topological modeler mainly developed by Frédéric Vidil and Guillaume Damiand (http://moka-modeller.sourceforge.net/). However, Moka was based on Generalized maps (and not Combinatorial maps), and the design was not Cgal "compatible". Thus, Guillaume Damiand started to develop a totally new package by mixing ideas taken from Moka with the design of the Halfedge data structure package of Cgal. Andreas Fabri and Sébastien Loriot contributed to the design, the coding, and to the documentation of the package, and Laurent Rineau helped for the design. Emma Michel contributed to the manual. Monique Teillaud and Bernd Gaertner contributed to the manual by giving useful remarks, really numerous and detailed for Monique.

Footnotes